%!TEX program = xelatex
\documentclass[UTF8]{article}
\usepackage{graphicx}
\usepackage{setspace}
% \usepackage{ctex}
\usepackage{indentfirst}
\setlength{\parindent}{2em}  % 用于首行缩进

\usepackage{amsmath}
\usepackage{amsthm} % 使用定理环境
\usepackage{amssymb}

% \usepackage{geometry}
% \geometry{a4paper,scale=0.8}

\usepackage{geometry}
\geometry{a4paper,left=2.0cm,right=2.0cm,top=3.0cm,bottom=3.0cm}
\setstretch{1.5}   %  改变行间距
% \newgeometry{left = 2 cm, top= 3 cm}

\title{Outline}
\author{Dis\cdot count}
% \date{Feb 2019}

\newtheorem{thm}{\hspace{2em}Theorem}
\newtheorem{lem}{\hspace{2em}Lemma}
\newtheorem{pf}{\hspace{2em}Proof}
\newtheorem{remark}{\hspace{2em}Remark}
%  \newtheorem{def}{Definition}  doesnt work


\begin{document}

\maketitle{}


\section{The Lemma and Theorem}

This outline shows how to solve the IPU game with alternative machines.

Here, I paste some Lemmas and Theorems at the beginning.

\begin{lem}\label{lem1}

The value at the extreme points of the sub-intervals $I_i$ can be calculated with processing times $t_i$ by comparing the costs of the grand coalitions where all the players use two adjacent numbers of machines.

\end{lem}

\begin{thm}\label{thm1}

$\omega(P)$ is piecewise linear, and convex in price P at each sub-interval $[P_L(m,V),P_H(m,V)]$ in $[0,P^*] $.

\end{thm}

\begin{thm}\label{thm2}

According to the foregoing description, we have the equation $P_L(V,1)=P_L(V,2)+\cdots+P_L(V,n)=\sum_{i=2}^n P_L(V,i)$.

\end{thm}

\begin{thm}\label{thm3}

The subsidy is always zero when the number of using machines, m, is larger than $\frac{n}{2}$.

\end{thm}


\begin{thm}\label{thm4}
The sum of absolute values of slopes at both sides of $P_L(V,i)$ is 1.
When the number of machines used is 1, the range of slopes of the line segments in the interval is $\left( -1 , -\frac{1}{n-1} \right]$, and the number of breakpoints is $ O(v^2) $.
\end{thm}


\begin{thm}\label{thm5}

The original problem is equivalent to using only one machine for all coalitions except the grand coalition.

\end{thm}


\begin{thm}\label{thm6}

The IPU game with alternative machines can be solved in polynomial time.

\end{thm}


\section{The approach}


As we all know, the cost arised from the partial players in the grand coalition ($c(s)$) can be calculated handily by the SPT rule. (The corresponding conclusion see Lemma \ref{lem1}) Meanwhile, inspired by the paper (Please refer to Liu et.al.2018), we have the following approach to solve this game.


There is an effective domain $[0, P^*]$, where the grand coalition may need a subsidy from the external to maintain the balance.
(The corresponding conclusion see Theorem \ref{thm1} and \ref{thm2} where $P^* = P_L(V,1)$).


For the effective domain, we just need to divide this interval into several parts and the breakpoints are denoted as $P_L(V,i), i = 1,2,\ldots,n$.  At first, we don't need to calculate the initial part because at this part the corresponding subsidy is 0 always. (The corresponding conclusion see Theorem \ref{thm3}) Then we just need to focus on the latter part which shows some interesting properties we presents above.


As we've already known that $P_L(V,i), i = 1,2,\ldots,n$ can be obtained by Lemma \ref{lem1} and Theorem \ref{thm2}, we just need to follow the CP approach (Algorithm 3 in Liu et.al.2018) to calculate the weak derivatives at each sub-interval $[P_L(m,V),P_H(m,V)]$ where the corresponding derivative is $m_V-\sum_{s\in S\setminus\{V\}} \rho_s$.

Then use IPC Algorithm (Algorithm 1 in Liu et.al.2018) which will return all the breakpoints during the $[0, P^*]$ to obtain the subsidy $\omega(P)$.

Notice that we can calculate the characteristic function $c(s)$ easily according to Theorem \ref{thm5}, we can formulate Theorem \ref{thm6}. Until here, we've solved the IPU game with alternative machines.


\end{document}
